This invention relates to a transmission queue managing system used in a packet switch, in particular, to a transmission queue managing system for an output buffered switching system.
As a method for controlling traffic congestion in a packet communication network, a tail-drop method, a random drop on full method, a random early detection (which may be abbreviated to RED) method and the like are well known for the output buffered switching system.
The tail-drop method is a simple method that following packets are dropped or discarded after a transmission queue is fully filled by preceding packets.
The random drop on full method is that some of packets filling a transmission queue are dropped at random when the transmission queue is fully filled by the packets.
The RED method is that following packets are selectively dropped by the use of statistical calculation when the number of preceding packets queued in a transmission queue reaches a predetermined threshold. The probability that each of the following packets is dropped is in proportion to the number of all packets queued in the transmission queue.
However, above-mentioned methods have a common problem that packets are dropped regardless of effect on controlling traffic congestion. That is, these methods can not efficiently control the traffic congestion.
If packets are selected on the basis of their header information to drop them, the traffic congestion will be more efficiently controlled. As methods that header information is referred to drop or discard frames or cells, some methods for providing a plurality of service classes are known.
For example, a frame relay control method is disclosed in Japanese Unexamined Patent Publication No. 11-68835. The frame relay control method prepares two transmission queues in a frame relay switch. One of the transmission queues is a normal queue while the other is a discarding priority queue. When a frame including discarding priority information is received, the frame relay switch stores the frame in the discarding priority queue. The frame relay switch collectively discards all frames stored in the discarding priority queue when congestion is detected in a destination of the frames.
Moreover, Japanese Patent Publication No. 2886976 discloses a service class control method for discarding cells in each class to avoid traffic congestion in an ATM switch. The ATM switch using the method has a plurality of buffer memories corresponding to service classes respectively. Cells received by the ATM switch are stored in the buffer memories according to their service classes represented by their header information. In each of the buffer memories, all cells are discarded when the number of the cells reaches a predetermined threshold.
Furthermore, Japanese Unexamined Patent Publication No. 11-510014 discloses a frame discharging method using a cell loss priority mark. A communication apparatus using the method compares the number of cells stored in a buffer with both of low and high thresholds whenever a cell including an end of file marker is received. If the number of the cells stored in the buffer is equal to or more than the low threshold and smaller than the high threshold, following cells each of which includes the cell loss priority marks are discarded until detection of the next end of file marker. When the number of the cells stored in the buffer is equal to or more than the high threshold, following cells are discarded regardless of the cell loss priority marks until detection of the next end of file marker.
Still furthermore, Japanese Unexamined Patent Publication No. 10-13427 discloses a node which discards cells requesting a specific service class on the basis of both of a connection identifier and a priority.
However, the above-mentioned four methods referring to the header information are not always effective in avoiding or controlling traffic congestion. This is because those methods described above only drops congested packets in an orderly manner or at random, and they are not capable of selectively dropping packets, based on packet header information, which would have most effect on controlling traffic congestion.